package com.interview.javabase.algorithm;

import org.springframework.util.CollectionUtils;

import java.util.Arrays;
import java.util.List;

/**
 * @author: zsg
 * @description:
 * @date: 2019/8/17 16:27
 * @modified:
 */
public class HandWriteLinked {

    public static void main(String[] args) {
//        LinkedNode head = createLinked(Arrays.asList(1, 3, 2, 4, 5, 3));
        LinkedNode head = createRecursionLinked(Arrays.asList(7, 8, 9, 10, 11, 12));
        LinkedNode second = createRecursionLinked(Arrays.asList(5, 6, 7, 15, 17, 21));
//        LinkedNode revertLinked = revertLinked(head);
//        deleteNode(head, 3);
//        LinkedNode listNode = addNode(null, 2);
//        updateNode(head, 3, 8);
//        LinkedNode revertLinked = printRevertLinked(head);
//        LinkedNode listNode = MergeLinked(head, second);
//        printLinked(listNode);
        int i = linkedLength(head);
        System.out.println(i);
    }

    /**
     * 创建大量节点
     *
     * @param list
     * @return
     */
    public static LinkedNode createLinked(List<Integer> list) {
        LinkedNode head = null;
        LinkedNode temp = null;
        for (int i = 0; i < list.size(); i++) {
            LinkedNode linkedNode = new LinkedNode(list.get(i));
            if (temp != null) {
                temp.next = linkedNode;
            } else {
                head = linkedNode;
            }
            temp = linkedNode;
        }
        return head;
    }

    /**
     * 递归创建
     *
     * @param list
     * @return
     */
    public static LinkedNode createRecursionLinked(List<Integer> list) {

        if (CollectionUtils.isEmpty(list)) {
            return null;
        }

        LinkedNode newNode = new LinkedNode(list.get(0));
        newNode.next = createRecursionLinked(list.subList(1, list.size()));
        return newNode;
    }

    /**
     * 添加节点
     *
     * @param head
     * @param value
     * @return
     */
    public static LinkedNode addNode(LinkedNode head, int value) {

        if (head == null) {
            head = new LinkedNode(value);
            return head;
        }

        LinkedNode temp = head;
        while (temp != null) {
            temp = temp.next;
        }

        temp.next = new LinkedNode(value);

        return head;
    }

    /**
     * 删除指定位置的节点
     *
     * @param head
     * @param index
     */
    public static void deleteNode(LinkedNode head, int index) {
        int length = linkedLength(head);
        if (length < index) {
            System.out.println("删除失败");
            return;
        }

        LinkedNode temp = head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }

        if (temp.next.next == null) {
            // last node
            temp.next = null;
        } else {
            temp.next = temp.next.next;
        }
    }

    /**
     * 反转单链表
     *
     * @param head
     * @return
     */
    public static LinkedNode revertLinked(LinkedNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        LinkedNode linkedNode = revertLinked(head.next);
        head.next.next = head;
        head.next = null;
        return linkedNode;
    }

    /**
     * 修改节点的值
     *
     * @param head
     * @param index
     * @param changeValue
     */
    public static void updateNode(LinkedNode head, int index, int changeValue) {
        int length = linkedLength(head);
        if (length < index) {
            System.out.println("删除失败");
            return;
        }


        LinkedNode temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }

        temp.val = changeValue;
    }

    /**
     * 计算链表的长度
     *
     * @param head
     * @return
     */
    public static int linkedLength(LinkedNode head) {
        LinkedNode temp = head;

        int length = 0;
        while (temp != null) {
            temp = temp.next;
            length++;
        }

        return length;
    }

    /**
     * 打印节点
     *
     * @param head
     */
    public static void printLinked(LinkedNode head) {

        LinkedNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
    }

    /**
     * 反向打印单链表
     *
     * @param head
     */
    public static LinkedNode printRevertLinked(LinkedNode head) {

        if (head == null) {
            return head;
        }

        if (head.next == null) {
            System.out.println(head.val);
            return head;
        }

        LinkedNode revertLinked = printRevertLinked(head.next);
        System.out.println(head.val);

        return revertLinked;
    }

    /**
     * 合并两个有序的单链表
     *
     * @param first
     * @param second
     */
    public static LinkedNode MergeLinked(LinkedNode first, LinkedNode second) {

        LinkedNode tempHead = new LinkedNode(0);

        LinkedNode pre = first;
        LinkedNode next = first.next;

        LinkedNode secondTemp = second;

        while (next != null) {
            if (pre.val <= secondTemp.val && next.val >= secondTemp.val) {
                LinkedNode linkedNode = new LinkedNode(secondTemp.val);
                pre.next = linkedNode;
                linkedNode.next = next;
                pre = linkedNode;
                secondTemp = secondTemp.next;
            } else if (pre.val < secondTemp.val && next.val < secondTemp.val) {

                if (next.next == null) {
                    next.next = secondTemp;
                    break;
                }

                next = next.next;
                pre = pre.next;
            } else if (pre.val > secondTemp.val && secondTemp != null) {

                if (secondTemp.next == null) {
                    secondTemp.next = pre;
                    tempHead.next = second;
                    break;
                } else if (pre.val <= secondTemp.next.val){
                    LinkedNode linkedNode = secondTemp.next;

                    secondTemp.next = pre;
                    tempHead.next = second;

                    secondTemp = linkedNode;

                } else {
                    secondTemp = secondTemp.next;
                }
            }
        }

        return tempHead.next;
    }
}
